package leetcode_2301_2400;

import java.util.HashSet;
import java.util.Set;

public class LeeCode_2354 {
    public static void main(String[] args) {
        System.out.println(countExcellentPairs(new int[]{1, 2, 3, 1}, 3));
    }
    private static long countExcellentPairs(int[] nums, int k) {
        int[] tab = new int[33];
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
                tab[Integer.bitCount(num)]++;
            }
        }
        long ans = 0;
        for (int i = 0; i < tab.length; i++) {
            for (int j = Math.max(k - i, 0); j < tab.length; j++) {
                ans += (long) tab[i] * tab[j];
            }
        }
        return ans;
    }
}
